class Node(object):
    """节点类"""
    def __init__(self, root=None, lc=None, rc=None):
        self.root = root
        self.lc = lc
        self.rc = rc

    # 先序遍历递归
    def preOrder(self, tree):
        if tree is None:
            return
        else:
            print(self.root)
            self.preOrder(self.lc)
            self.preOrder(self.rc)

    # 先序遍历递归
    def midOrder(self, tree):
        if tree is None:
            return
        else:
            self.midOrder(self.lc)
            print(self.root)
            self.midOrder(self.rc)


# 先序遍历-非递归 pre-order
def front_tree(tree):
    stack = []
    # 按照层级便利的形式，先把右节点入栈，在入左节点，然后打印弹出值
    stack.append(tree)
    while stack:
        node = stack.pop()
        print(node.root)
        if node.rc:
            stack.append(node.rc)
        if node.lc:
            stack.append(node.lc)


# 中序遍历-非递归
def middle_tree(tree):
    # 先找最左的子节点，沿途入栈，然后保证每次都从左叶子节点开始弹出，弹出然后入栈右叶子节点
    stack = []
    stack.append(tree)
    while stack and tree:
        while tree:
            stack.append(tree)
            tree = tree.lc
        if stack:
            node = stack.pop()
            print(node.root)
            tree = tree.rc


# 后续遍历-非递归
def after_tree(tree):
    stack = []
    flag = []
    stack.append(tree)
    while stack and tree:
        while tree:
            stack.append(tree)
            flag.append(0)
            tree = tree.lc
        if stack:
            top = stack[-1]
            if top.rc and not flag[-1]:
                flag[-1] = -1
                tree = top.rc
            else:
                flag.pop()
                print(stack.pop().root)


# leetcode 112 路径总和
# leetcode 124 二叉树最大路径和
# leetcode 145 二叉树后序遍历非递归

if __name__ == '__main__':
    tree = Node('A', Node('B', Node('D', 0, 0), Node('E', 0, 0)), Node('C', Node('F', 0, 0), Node('G', 0, 0)))
    # front_tree(tree)
    middle_tree(tree)



